【题解】 [NOI2005]维护数列 Splay luoguP2042 | Qiuly's blog!

【题解】 [NOI2005]维护数列 Splay luoguP2042

Posted on | In | Comments:

神奇的题目。

网上说什么做了这道题 $Splay$ 就差不多了，嗯对窝也这么觉得。于是终于码掉了。

主要涉及的操作还是提取区间，我们组需要将 $l-1$ 提取至 $root$ ， 然后将 $r+1$ 提取至 $l-1$ 的下方，最终询问的 $l,r$ 区间的 $Splay$ 就是 $r+1$ 的左孩子。

这个时候该输出的就输出，该打标记的就打标记就好了。

至于插入的话我们可以先将所有需要插入的结点 $build$ 成一棵树，然后直接挂到 $r+1$ 的左孩子即可。

但是毒瘤出题人卡空间，于是我们需要将删除的结点全部重新应用，就像垃圾回收那样，搞个栈就行了。

最后因为怕 $l-1$ 和 $r+1$ 出界我们还需要新增两个”哨兵结点”，这样子的话需要提取的结点都加上了 $1$ ，提取区间变动的两个节点就变成 $l$ 和 $r+2$ 了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=5.5e5+7;
const int inf=1e8;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Splay {
    int root,cnt;
    int ch[N][2],sz[N],fa[N],val[N],tag[N],rev[N];
    int sum[N],lmax[N],rmax[N],smax[N];
    int date[N],trash[N],top;

    Splay(){root=cnt=top=0;}
    bool chk(int x) {return ch[fa[x]][1]==x;}
    void clear(int node) {
        ch[node][0]=ch[node][0]=sz[node]=fa[node]=val[node]=0,
        rev[node]=sum[node]=lmax[node]=rmax[node]=smax[node]=0;
        tag[node]=inf;
    }
    int MKN() {
        int node;
        node=top?trash[top--]:++cnt;
        clear(node);return node;
    }
    void pushup(int x) {
        int l=ch[x][0],r=ch[x][1];
        sz[x]=sz[l]+sz[r]+1;
        sum[x]=sum[l]+sum[r]+val[x];
        lmax[x]=max(lmax[l],sum[l]+val[x]+lmax[r]);
        rmax[x]=max(rmax[r],sum[r]+val[x]+rmax[l]);
        smax[x]=max(rmax[l]+lmax[r]+val[x],max(smax[l],smax[r]));
    }
    void pushdown(int x) {
        int l=ch[x][0],r=ch[x][1];
        if(tag[x]!=inf) {
            if(l) val[l]=tag[l]=tag[x],sum[l]=tag[x]*sz[l];
            if(r) val[r]=tag[r]=tag[x],sum[r]=tag[x]*sz[r];
            if(tag[x]>=0) {
                if(l) lmax[l]=rmax[l]=smax[l]=sum[l];
                if(r) lmax[r]=rmax[r]=smax[r]=sum[r];
            } else if(tag[x]<0) {
                if(l) lmax[l]=rmax[l]=0,smax[l]=tag[x];
                if(r) lmax[r]=rmax[r]=0,smax[r]=tag[x];
            }
            tag[x]=inf;
        }
        if(rev[x]) {
            if(l) swap(ch[l][0],ch[l][1]),swap(lmax[l],rmax[l]),rev[l]^=1;
            if(r) swap(ch[r][0],ch[r][1]),swap(lmax[r],rmax[r]),rev[r]^=1;
            rev[x]=0;
        }
    }
    void rotate(int x) {
        int y=fa[x],z=fa[y];
        pushdown(y),pushdown(x);
        int k=chk(x),v=ch[x][k^1];
        ch[z][chk(y)]=x,fa[x]=z,ch[y][k]=v,fa[v]=y,
        ch[x][k^1]=y,fa[y]=x;pushup(y),pushup(x);
    }
    void splay(int x,int gola=0) {
        while(fa[x]!=gola) {
            if(fa[fa[x]]!=gola)
                rotate(chk(x)^chk(fa[x])?x:fa[x]);
            rotate(x);
        }if(!gola) root=x;
    }
    int kth(int x) {
        int pos=root;
        while(pos) {
            pushdown(pos);
            if(x<=sz[ch[pos][0]]) pos=ch[pos][0];
            else {
                x-=sz[ch[pos][0]]+1;
                if(!x) return pos;
                pos=ch[pos][1];
            }
        }return 0;
    }
    int build(int l,int r,int f) {
        if(l>r) return 0;
        int x=MKN(),mid=(l+r)>>1;
        ch[x][0]=build(l,mid-1,x),ch[x][1]=build(mid+1,r,x);
        val[x]=date[mid],fa[x]=f,pushup(x);
        return x;  
    }
    void trashcan_node(int x) {
        if(!x) return;
        trash[++top]=x,trashcan_node(ch[x][0]),trashcan_node(ch[x][1]);
    }
    int split(int&l,int&r,int pos,int tot) {
        l=kth(pos),r=kth(pos+tot+1);splay(l),splay(r,l);
    }
    void work_insert() {
        int pos,tot,l,r;
        IN(pos),IN(tot);
        for(int i=1;i<=tot;++i) IN(date[i]);
        split(l,r,pos+1,0);
        ch[r][0]=build(1,tot,r),pushup(r),pushup(root);
    }
    void work_delete() {
        int pos,tot,l,r;
        IN(pos),IN(tot),split(l,r,pos,tot);
        trashcan_node(ch[r][0]),ch[r][0]=0,pushup(r),pushup(root);
    }
    void work_same() {
        int pos,tot,c,l,r;
        IN(pos),IN(tot),IN(c),split(l,r,pos,tot);
        int p=ch[r][0];
        if(p) {
            val[p]=tag[p]=c,sum[p]=c*sz[p];
            if(c>=0) lmax[p]=rmax[p]=smax[p]=sum[p];
            else if(c<0) lmax[p]=rmax[p]=0,smax[p]=c;
        }pushup(r),pushup(root);
    }
    void work_rev() {
        int pos,tot,l,r;
        IN(pos),IN(tot),split(l,r,pos,tot);
        if(ch[r][0]) {
            swap(ch[ch[r][0]][0],ch[ch[r][0]][1]);
            swap(lmax[ch[r][0]],rmax[ch[r][0]]);
            rev[ch[r][0]]^=1;
        }pushup(r),pushup(root);
    }
    void work_sum() {
        int pos,tot,l,r;
        IN(pos),IN(tot),split(l,r,pos,tot);
        printf("%d\n",sum[ch[r][0]]);
    }
    void work_max() {
        int l=kth(1),r=kth(sz[root]);splay(l),splay(r,l);
        printf("%d\n",smax[ch[r][0]]);
    }
}T;

int n,m;
char op[25];

int main() {
    // freopen("testdata.in","r",stdin);
    // freopen("myout.out","w",stdout);
    IN(n),IN(m);
    for(int i=1;i<=n;++i) IN(T.date[i+1]);
    T.smax[0]=T.date[1]=-inf,T.date[n+2]=inf;
    T.root=T.build(1,n+2,0);
    while(m--) {
        scanf("%s",op);
        if(op[0]=='M') {
            if(op[3]=='E') T.work_same();
            else T.work_max();
        } 
        else if(op[0]=='I') T.work_insert();
        else if(op[0]=='D') T.work_delete();
        else if(op[0]=='R') T.work_rev();
        else if(op[0]=='G') T.work_sum();
    }
    return 0;
}

哎离 $HNOI2019$ 不远了，感觉多多更博增加 $RP$ …… $QwQ$

本文标题:【题解】 [NOI2005]维护数列 Splay luoguP2042

文章作者:Qiuly

发布时间:2019年04月02日 - 00:00

最后更新:2019年04月02日 - 10:06

原始链接:http://qiulyblog.github.io/2019/04/02/[题解]luoguP2042/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。